package org.example.SolutionNew003;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DoubleTree013 {
    public static void main(String[] args) {
        DoubleTree013 dt=new DoubleTree013();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right = new TreeNode(4);
        root.left.left = new TreeNode(3);
        System.out.println(dt.pathSum(root,6));
    }

    int res=0;
    public int pathSum1(TreeNode root, int targetSum) {
        if(root==null) return 0;
        List<Long> list=new ArrayList<>();
        searchAllTheTree(root,targetSum,list);
        return res;
    }

    public void searchAllTheTree(TreeNode root, int targetSum, List<Long> lsit) {
        if(root==null) return;
        Long val=(long)root.val;
        List<Long> tmpList=new ArrayList<>();
        tmpList.add(val);
        if(val==targetSum) res++;
        for(Long num:lsit) {
            long temp=num+val;
            if(temp==targetSum) res++;
            tmpList.add(temp);
        }
        searchAllTheTree(root.left,targetSum,tmpList);
        searchAllTheTree(root.right,targetSum,tmpList);
    }

    //一个不会有太多额外空间的方法
    //把每个节点都当一次头节点向下计算
    public int pathSum2(TreeNode root, int targetSum) {
        if(root==null) return 0;
        int res=sumFromTheNode(root,(long)targetSum);
        res+=pathSum2(root.left,targetSum);
        res+=pathSum2(root.right,targetSum);
        return res;
    }

    public int sumFromTheNode(TreeNode root, Long targetSum) {
        if(root==null) return 0;

        int res=0;
        if(root.val==targetSum) res++;
        res+=sumFromTheNode(root.left,targetSum-root.val);
        res+=sumFromTheNode(root.right,targetSum-root.val);
        return res;
    }

    //严格从上往下 前缀和
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> map=new HashMap<>();
        map.put(0L,1);
        return searchRes(root,map,targetSum,0);
    }

    public int searchRes(TreeNode root, Map<Long,Integer> map, int targetSum, long preSum) {
        if(root==null) return 0;

        Long cur=root.val+preSum;
        int res=map.getOrDefault(cur-targetSum,0);
        map.put(cur,map.getOrDefault(cur,0)+1);
        res+=searchRes(root.left,map,targetSum,cur);
        res+=searchRes(root.right,map,targetSum,cur);
        map.put(cur,map.getOrDefault(cur,0)-1);
        return res;
    }

}
